import java.util.ArrayList;
import java.util.List;

/**
 * 315. 计算右侧小于当前元素的个数
 * https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
 */
public class Solutions_315 {
    public static void main(String[] args) {
        int[] nums = {5, 2, 6, 1};  // output: {2, 1, 1, 0}
//        int[] nums = {5, 4, 3, 2, 1};  // output: {4, 3, 2, 1, 0}
//        int[] nums = {0, 2, 1};  // output: {0, 1, 0}

        List<Integer> result = countSmaller(nums);
        System.out.println(result);
    }

    private static int[] index = null;
    // ans[0] = 2，表示 nums[0] 的右侧有 2 个更小的元素
    private static int[] ans = null;
    // 元素排序时，用于临时记录下排序后，索引上对应的新索引
    private static int[] tempIndex = null;
    // 元素排序时，用于临时记录下排序后，索引上对应的值
    private static int[] tempNum = null;

    /**
     * 解法一：归并排序（7ms）
     * 解题思路：通过归并排序的方式，在排序完成后，合并两个数组的过程中，
     * 可以计算得到左侧数组中各个元素，在右侧数组中存在小于该元素的个数（j - 1 - mid 个）
     *
     * 难点：排序后，元素的位置相应地变化，那么如何给 ans 数组赋值呢？
     * 解决方案是：维护一个 index 数组
     * index[0] = 1，表示现在索引 0 上的元素，存储的是排序前索引 1 上的元素
     * index[2] = 3，表示现在索引 2 上的元素，存储的是排序前索引 3 上的元素
     * 那么通过 ans[index[0]] 的方式，就可以对应到原本的索引
     */
    public static List<Integer> countSmaller(int[] nums) {
        int len = nums.length;
        index = new int[len];
        ans = new int[len];
        tempIndex = new int[len];
        tempNum = new int[len];

        for (int i = 0; i < len; i++) {
            // 默认不变，索引 0 上对应的就是索引 0
            index[i] = i;
        }
        int left = 0, right = nums.length - 1;
        sort(nums, left, right);
        List<Integer> res = new ArrayList<>();
        for (int num : ans) {
            res.add(num);
        }
        return res;
    }

    public static void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        // [left, mid] 部分完成排序及计算
        sort(nums, left, mid);
        // [mid, right] 部分完成排序及计算
        sort(nums, mid + 1, right);
        if (nums[mid] <= nums[mid + 1]) {
            // 剪枝：右侧部分都是大于等于左侧部分的，不需要再排放和计算了
            return;
        }

        // 合并左右数组到 arr 中，合并过程中完成排序及计算
        // 左数组：[left, mid]
        // 右数组：[mid, right]
        int i = left, j = mid + 1, idx = left;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tempNum[idx] = nums[i];
                // 索引 index[i] 移动到了索引 idx 下
                tempIndex[idx] = index[i];
                // 记录下右侧比 nums[i] 小的元素，即右侧数组中的 [0, j] 部分
                // j 需要减 1，因为 j 已经 ++ 过
                int originIndex = index[i];
                ans[originIndex] += (j - 1 - mid);
                i ++;
            } else {
                tempNum[idx] = nums[j];
                // 索引 index[j] 移动到了索引 idx 下
                tempIndex[idx] = index[j];
                j ++;
            }
            idx ++;
        }
        while (i <= mid) {
            tempNum[idx] = nums[i];
            // 索引 index[i] 移动到了索引 idx 下
            tempIndex[idx] = index[i];
            // 记录下右侧比 nums[i] 小的元素，即右侧数组中的 [0, j] 部分
            // j 需要减 1，因为 j 已经 ++ 过
            int originIndex = index[i];
            ans[originIndex] += (j - 1 - mid);
            i ++;
            idx ++;
        }
        while (j <= right) {
            tempNum[idx] = nums[j];
            // 索引 index[j] 移动到了索引 idx 下
            tempIndex[idx] = index[j];
            j ++;
            idx ++;
        }

        // 将已排序的数组 arr 中的元素，添加到 nums 数组的 [left, right] 中
        for (int k = left; k <= right; k++) {
            // 排序完成后，更新索引和值
            index[k] = tempIndex[k];
            nums[k] = tempNum[k];
        }
    }
}
